# -*- coding: utf-8 -*-

"""剑指 Offer II 073. 狒狒吃香蕉
狒狒喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
狒狒可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。  
狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：
输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：
输入: piles = [30,11,23,4,20], H = 6
输出: 23

提示：
1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9"""


class Solution:
    """此题有两个条件：1）要吃掉所有的香蕉；2）最小速度
    
    1.边界情况：
        H < hi:=len(piles) --> null
        H = hi  --> max(piles)
        H > hi  --> 计算
    
    2. 前置条件先将堆排序

    3. 将不用分批吃的堆分出，条件，piles[i] <= sum(piles)//H; 2*hi_left:=len(left_piles) <= H（暂没有使用）
    4. 后面剩余的堆，可能都要分批吃了，怎么寻找最小K
        a. 用二分法，初始 mini:=max(1, eating, average), maxi:=max(left_piles)
            如果初始mini满足，则K=mini
            取middle，计算middle用时，如果满足，maxi <- 前移; 如果不满足，mini -> 后移
            循环终止条件：maxi-mini=1
        b. 对于每次的middle是否满足的判断，可以用阶梯来计算，分别取1阶、2阶、3阶...的最后一个元素（二分查找，小于x阶最大期望值（x*middle）的最大元素）
            可以在此过程中与 h 的计算耦合起来
            ***实践证明递增取阶，对于变化较大的两个元素，如 per:=1, next:=9999999, k:=2 的情况，就有很多无用的阶，导致超时
        c. 在 b 的基础上，改进，每次获取一个元素的所属阶，二分查找该阶最后一个元素，进入该阶后一个元素，依次计算"""
    def minEatingSpeed(self, piles, h: int) -> int:
        def koko_divide(bananas, hour):
            if bananas % hour:
                return bananas//hour+1
            else:
                return bananas//hour
        
        def binsearch_left_LE_max(head, tail, count):
            if piles[head]>count:
                return
            
            if piles[tail]<=count:
                return tail

            while tail-head > 1:
                middle = (head+tail)//2
                if piles[middle] <= count:
                    head = middle
                else:
                    tail = middle
            return head

        def try_eating_by_skip(k):
            # print('----    %s    ----' % k)
            start, total_times = divide_start, 0
            # print(start, hour)
            while start < hi:
                t = koko_divide(piles[start], k)
                fartest = binsearch_left_LE_max(start, hi-1, k*t)
                if not fartest:
                    fartest = start
                total_times += t*(fartest-start+1)    
                start = fartest + 1
            return total_times <= hour
        
        hour = h
        hi = len(piles)
        if hour < hi:
            return
        elif hour == hi:
            return max(piles)
        elif sum(piles) <= hour:
            return 1
        
        piles.sort()

        avg_k = koko_divide(sum(piles), hour)
        divide_start = binsearch_left_LE_max(0, hi-1, avg_k)
        if divide_start:
            divide_start += 1
        else:
            divide_start = 0
        hour = hour-divide_start

        mini_k, maxi_k = max(2, avg_k), max(piles)
        if try_eating_by_skip(mini_k):
            return mini_k 
        
        while maxi_k-mini_k > 1:
            middle_k = (mini_k+maxi_k)//2
            if try_eating_by_skip(middle_k):
                maxi_k = middle_k
            else:
                mini_k = middle_k
        
        return maxi_k
        

if __name__ == '__main__':
    so = Solution()
    print(so.minEatingSpeed(piles = [3,6,7,11], h = 8))
    print(so.minEatingSpeed([30,11,23,4,20], h = 5))
    print(so.minEatingSpeed([30,11,23,4,20], h = 6))
    print(so.minEatingSpeed([312884470], h = 312884469))
    print(so.minEatingSpeed([332484035,524908576,855865114,632922376,222257295,690155293,112677673,679580077,337406589,290818316,877337160,901728858,679284947,688210097,692137887,718203285,629455728,941802184], 823855818))
